package com.mypaper.dag;

import com.mypaper.elem.LinkedListNode;
import com.mypaper.elem.TaskAttribute;
import com.mypaper.elem.TaskNode;
import com.mypaper.list.ListPriority;
import com.mypaper.list.StackClass;
import com.mypaper.list.UnorderLinkedList;



public class DAG {
	/*
	 * DAG图，用于描述application的信息，包括通信，计算平均Cost，在每个处理器上的Cost，任务出度等
	 */
	public int vertexNum;
	public int procNum;
	public float[] vertexAverWeight;
	public float[][] vertexWeight;
	public float[][] edgeWeight;
	public float[] btLevel;
	public float CPLength=0;
	public ListPriority prior;//HEFT的优先级队列
	public ListPriority priorRever;//HEFT的反队列，用于删除复制版本
	public ListPriority priorHCP;
	public ListPriority priorReverHCP;
	public ListPriority priorCPOP;
	public int[] outDegree;
	public int[] inDegree;
	public int selectedProcCPOP=-1;//CPOP中为CP任务选择的处理器
	
	public ListPriority priorHLD2;
	
	
	public DAG(){
		vertexNum=0;
		procNum=0;
		prior=new ListPriority();
		vertexWeight=new float[vertexNum][procNum];

		
		float sum;
		for(int i=0; i<vertexNum; i++){
			sum=0;
			for(int j=0; j<procNum; j++){
				sum+=vertexWeight[i][j];
			}
			vertexAverWeight[i]=sum/procNum;
		}
		edgeWeight=new float[vertexNum][vertexNum];
	}
	
	public DAG(int vertexNum, int procNum, float[][] vertexWeight, float[][] edgeWeight){
		this.vertexNum=vertexNum;
		this.procNum=procNum;
		this.vertexWeight=new float[vertexNum][procNum];
		this.vertexAverWeight=new float[vertexNum];
		this.edgeWeight=new float[vertexNum][vertexNum];
		this.prior=new ListPriority();
		this.priorRever=new ListPriority();
		this.priorHCP=new ListPriority();
		this.priorCPOP=new ListPriority();
		this.priorReverHCP=new ListPriority();
		this.outDegree=new int[vertexNum];
		this.inDegree=new int[vertexNum];
		
		for(int i=0; i<vertexNum; i++)
			for(int j=0; j<vertexNum; j++){
				if(edgeWeight[i][j]!=0)
					outDegree[i]++;
				if(edgeWeight[j][i]!=0)
					inDegree[i]++;
			}
		for(int i=0; i<vertexNum; i++)
			for(int j=0; j<procNum; j++)
				this.vertexWeight[i][j]=vertexWeight[i][j];
		
		
		/*for(int i=0; i<vertexNum; i++){
			this.vertexAverWeight[i]=Float.MAX_VALUE;
			for(int j=0; j<procNum; j++){
				if(this.vertexAverWeight[i]>this.vertexWeight[i][j]){
					this.vertexAverWeight[i]=this.vertexWeight[i][j];
				}
			}
		}*/
		
		for(int i=0; i<vertexNum; i++)
			for(int j=0; j<vertexNum; j++){
				this.edgeWeight[i][j]=edgeWeight[i][j];
			}
		
		/*this.vertexAverWeight[0]=1;
		this.vertexAverWeight[1]=1;
		this.vertexAverWeight[2]=1;
		this.vertexAverWeight[3]=1;
		this.vertexAverWeight[4]=1;
		
		this.vertexAverWeight[5]=4;
		this.vertexAverWeight[6]=1;
		this.vertexAverWeight[7]=2;
		this.vertexAverWeight[8]=1;
		this.vertexAverWeight[9]=1;*/
		                   
		
		/*for(int i=0; i<vertexNum; i++){
			this.vertexAverWeight[i]=Float.MAX_VALUE;
			for(int j=0; j<procNum; j++){
				if(this.vertexAverWeight[i]>this.vertexWeight[i][j]){
					this.vertexAverWeight[i]=this.vertexWeight[i][j];
				}
			}
		}*/
		
		//proirBLevel();
		//proirHCPFD();
		//priorCPOP();
		
	}
	
	public void calcBLPrior(){
		for(int i=0; i<vertexNum; i++){
			float sum=0;
			for(int j=0; j<procNum; j++){
				sum+=vertexWeight[i][j];
			}
			this.vertexAverWeight[i]=sum/procNum;
		}
		proirBLevel();
	}
	
	public void calcHCPrior(){
		proirHCPFD();
	}
	public void calcMMPrior(){
		for(int i=0; i<vertexNum; i++){
			this.vertexAverWeight[i]=Float.MAX_VALUE;
			for(int j=0; j<procNum; j++){
				if(this.vertexAverWeight[i]>this.vertexWeight[i][j]){
					this.vertexAverWeight[i]=this.vertexWeight[i][j];
				}
			}
		}
		
		proirBLevel();
	}
	
	public void print(){
		System.out.println("DAG's attribute:");
		System.out.println("vertex number: "+vertexNum);
		System.out.println("processor number: "+procNum);
		System.out.println("The computation cost:");
		
		for(int i=0; i<vertexNum; i++){
			for(int j=0; j<vertexNum; j++){
				System.out.print(edgeWeight[i][j]+"\t");
			}
			System.out.println();
		}
		System.out.println();
		
		System.out.println("The average computation cost:");
		for(int i=0; i<vertexNum; i++){
			System.out.print(vertexAverWeight[i]+"\t");
		}
		System.out.println();
		System.out.println("The priority:");
		prior.print();
		System.out.println();
	}

	public float[] bLevelCal(){
		float[] blevel=new float[vertexNum];
		float maxBSucc=0;
		int[] outDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
			outDegreeBack[i]=outDegree[i];
		
		for(int i=0; i<vertexNum; i++){
			for(int j=vertexNum-1; j>=0; j--){
				if(outDegreeBack[j]==0){
					maxBSucc=0;
					for(int k=0; k<vertexNum; k++){
						if(edgeWeight[j][k]!=0){
							if(maxBSucc<edgeWeight[j][k]+blevel[k]){
								maxBSucc=edgeWeight[j][k]+blevel[k];
							}
						}
					}
					blevel[j]=vertexAverWeight[j]+maxBSucc;
					outDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeight[k][j]!=0 && outDegreeBack[k]>=0)
							outDegreeBack[k]--;
					}
					break;
				}
			}
		}
		return blevel;
	}
	
	public float[] tLevelCal(){
		float[] tlevel=new float[vertexNum];
		float maxTPrev=0;
		int[] inDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
			inDegreeBack[i]=inDegree[i];
		
		for(int i=0; i<vertexNum; i++){
			for(int j=0; j<vertexNum; j++){
				if(inDegreeBack[j]==0){
					maxTPrev=0;
					for(int k=0; k<vertexNum; k++){
						if(edgeWeight[k][j]!=0){
							if(maxTPrev<edgeWeight[k][j]+vertexAverWeight[k]+tlevel[k]){
								maxTPrev=edgeWeight[k][j]+vertexAverWeight[k]+tlevel[k];
							}
						}
					}
					tlevel[j]=maxTPrev;
					inDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeight[j][k]!=0 && inDegreeBack[k]>=0)
							inDegreeBack[k]--;
					}
					break;
				}
			}
		}
		return tlevel;
	}
	
	public void proirBLevel(){
		float[] bLevel=bLevelCal();
		TaskAttribute task=new TaskAttribute();
		for(int i=0; i<vertexNum; i++){
			task.setAttribute(i, bLevel[i]);
			prior.enDownList(task);
			priorRever.enUpList(task);
		}
	}
	
	public void priorCPOP(){
		float[] bLevel=bLevelCal();
		float[] tLevel=tLevelCal();
	
		btLevel=new float[vertexNum];
		for(int i=0; i<vertexNum; i++){
			btLevel[i]=bLevel[i]+tLevel[i];
		}
	
		TaskAttribute task=new TaskAttribute();

		for(int i=0; i<vertexNum; i++){
			if(CPLength<btLevel[i]){
				CPLength=btLevel[i];
			}
		}
		UnorderLinkedList CPList=new UnorderLinkedList();
		for(int i=0; i<vertexNum; i++){
			if(Math.abs(btLevel[i]-CPLength)<0.0001)//找CP上的任务
			{
				task.setAttribute(i, btLevel[i]);
				CPList.insertNode(task);//插入到队列
			}
		}
		//CPList.print();
		LinkedListNode CPNode=CPList.first;
		float minProc=Float.MAX_VALUE;
		float sumProc;
		
		for(int i=0; i<procNum; i++){	
			sumProc=0;
			CPNode=CPList.first;
			while(CPNode!=null){
				task=(TaskAttribute)CPNode.info;
				sumProc+=vertexWeight[task.getIndex()][i];
				CPNode=CPNode.next;
			}
			if(minProc>sumProc){
				minProc=sumProc;
				selectedProcCPOP=i;
			}
		}

		ListPriority backPriority=new ListPriority();
		
		for(int i=0; i<vertexNum; i++){
			if(inDegree[i]==0){
				task.setAttribute(i, btLevel[i]);
				backPriority.enDownList(task);//将入结点插入任务队列
			}
		}
		
		TaskNode backNode=backPriority.first;
		
		while(backNode!=null){
			//System.out.println();
			//priorCPOP.print();
			priorCPOP.enListLast(backNode.info);
			backPriority.popList();
			for(int j=0; j<vertexNum; j++){
				if(inDegree[j]>=0&&edgeWeight[backNode.info.index][j]!=0){
					inDegree[j]--;
					if(inDegree[j]==0){
						task.setAttribute(j, btLevel[j]);
						backPriority.enDownList(task);
					}
				}
			}
			backNode=backPriority.first;
		}
		//priorCPOP.print();
	}
	public void printPrior(){
		priorCPOP.print();
	}
	
	public float[] calcAEST(){
		float[] AEST=new float[vertexNum];
		int[] inDegreeBack=new int[vertexNum];
		float maxPare;
		for(int i=0; i<vertexNum; i++)
			inDegreeBack[i]=inDegree[i];
		
		for(int i=0; i<vertexNum; i++){
			for(int j=0; j<vertexNum; j++){
				if(inDegreeBack[j]==0){
					maxPare=0;
					if(j==0){
						AEST[j]=0;
					}else{
						for(int k=0; k<vertexNum; k++){
							if(edgeWeight[k][j]!=0){
								if(maxPare<edgeWeight[k][j]+AEST[k]+vertexAverWeight[k]){
									maxPare=edgeWeight[k][j]+AEST[k]+vertexAverWeight[k];
								}
							}
						}
						AEST[j]=maxPare;
					}
					
					inDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeight[j][k]!=0 && inDegreeBack[k]>=0)
							inDegreeBack[k]--;
					}
				}
			}
		}
		
		return AEST;
	}
	
	public float[] calcALST(float init){
		float minChild;
		float[] ALST=new float[vertexNum];
		
		int[] outDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
			outDegreeBack[i]=outDegree[i];
		
		for(int i=0; i<vertexNum; i++){
			for(int j=vertexNum-1; j>=0; j--){
				if(outDegreeBack[j]==0){
					minChild=Float.MAX_VALUE;
					if(j==vertexNum-1){
						ALST[j]=init;
					}else{
						for(int k=0; k<vertexNum; k++){
							if(edgeWeight[j][k]!=0){
								if(minChild>ALST[k]-edgeWeight[j][k]){
									minChild=ALST[k]-edgeWeight[j][k];
								}
							}
						}
						ALST[j]=minChild-vertexAverWeight[j];
					}
					
					outDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeight[k][j]!=0 && outDegreeBack[k]>=0)
							outDegreeBack[k]--;
					}
				}
			}
		}
		
		return ALST;
	}
	
	public void proirHCPFD()
	{
		boolean[] flagPush=new boolean[vertexNum];
		StackClass sClass=new StackClass(vertexNum);
		int[] outDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
			outDegreeBack[i]=outDegree[i];
		int[] inDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
			inDegreeBack[i]=inDegree[i];
		
		float[] AEST=calcAEST();
		float[] ALST=calcALST(AEST[vertexNum-1]);
		
		for(int i=0; i<vertexNum; i++)
			for(int j=vertexNum-1; j>=0; j--)
				if(outDegreeBack[j]==0){
					if(AEST[j]==ALST[j]){
						TaskAttribute newItem=new TaskAttribute(j,ALST[j]);
						sClass.push(newItem);
						flagPush[newItem.getIndex()]=true;
					}		
					outDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeight[k][j]!=0 && outDegreeBack[k]>=0)
							outDegreeBack[k]--;
					}
					break;
				}
		//构造堆栈

		while(!sClass.isEmpty()){
			TaskAttribute de=(TaskAttribute)sClass.top();//顶部元素
			if(inDegreeBack[de.getIndex()]==0){
				priorHCP.enListLast(de);
				priorReverHCP.enListFirst(de);
				sClass.pop();
				for(int k=0; k<vertexNum; k++){
					//当前节点的孩子节点入度减一
					if(edgeWeight[de.getIndex()][k]!=0 && inDegreeBack[k]>=0)
						inDegreeBack[k]--;
				}
			}else{			
				for(int i=0; i<vertexNum; i++)
					if(edgeWeight[i][de.getIndex()]!=0&&flagPush[i]!=true){
						sClass.push(new TaskAttribute(i,ALST[i]));
						flagPush[i]=true;
						break;
					}
			}
		}
	}
}
